public class Test {

    private void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private void creatHeap(int[] arr) {
        for (int parent = (arr.length - 1 - 1) / 2 ; parent >= 0 ; parent--) {
            siftDown(arr,parent,arr.length);
        }
    }

    private void siftDown(int[] arr, int parent, int size) {
        int child = 2 * parent + 1;
        while(child < size - 1) {
            if(child + 1 < size - 1 && arr[child+1] > arr[child]) {
                child++;
            }
            if(arr[parent] < arr[child]) {
                swap(arr,parent,child);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    public void heapSort(int[] arr) {
        if(arr == null || arr.length == 0) {
            return;
        }
        creatHeap(arr); // 建立大堆
        int end = arr.length - 1; //获取最后一个元素的下标
        //删除
        while(end > 0) {
            swap(arr,0,end);
            siftDown(arr,0,end + 1);
            end--;
        }
    }

    public static void main(String[] args) {

    }
}
